// Copyright (c) 2012 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "net/dns/host_cache.h"

#include "base/format_macros.h"
#include "base/stl_util.h"
#include "base/strings/string_util.h"
#include "base/strings/stringprintf.h"
#include "net/base/net_errors.h"
#include "testing/gtest/include/gtest/gtest.h"

namespace net {

namespace {

    const int kMaxCacheEntries = 10;

    // Builds a key for |hostname|, defaulting the address family to unspecified.
    HostCache::Key Key(const std::string& hostname)
    {
        return HostCache::Key(hostname, ADDRESS_FAMILY_UNSPECIFIED, 0);
    }

} // namespace

TEST(HostCacheTest, Basic)
{
    const base::TimeDelta kTTL = base::TimeDelta::FromSeconds(10);

    HostCache cache(kMaxCacheEntries);

    // Start at t=0.
    base::TimeTicks now;

    HostCache::Key key1 = Key("foobar.com");
    HostCache::Key key2 = Key("foobar2.com");
    HostCache::Entry entry = HostCache::Entry(OK, AddressList());

    EXPECT_EQ(0U, cache.size());

    // Add an entry for "foobar.com" at t=0.
    EXPECT_FALSE(cache.Lookup(key1, now));
    cache.Set(key1, entry, now, kTTL);
    EXPECT_TRUE(cache.Lookup(key1, now));
    EXPECT_TRUE(cache.Lookup(key1, now)->error() == entry.error());

    EXPECT_EQ(1U, cache.size());

    // Advance to t=5.
    now += base::TimeDelta::FromSeconds(5);

    // Add an entry for "foobar2.com" at t=5.
    EXPECT_FALSE(cache.Lookup(key2, now));
    cache.Set(key2, entry, now, kTTL);
    EXPECT_TRUE(cache.Lookup(key2, now));
    EXPECT_EQ(2U, cache.size());

    // Advance to t=9
    now += base::TimeDelta::FromSeconds(4);

    // Verify that the entries we added are still retrievable, and usable.
    EXPECT_TRUE(cache.Lookup(key1, now));
    EXPECT_TRUE(cache.Lookup(key2, now));
    EXPECT_NE(cache.Lookup(key1, now), cache.Lookup(key2, now));

    // Advance to t=10; key is now expired.
    now += base::TimeDelta::FromSeconds(1);

    EXPECT_FALSE(cache.Lookup(key1, now));
    EXPECT_TRUE(cache.Lookup(key2, now));

    // Update key1, so it is no longer expired.
    cache.Set(key1, entry, now, kTTL);
    EXPECT_TRUE(cache.Lookup(key1, now));
    EXPECT_EQ(2U, cache.size());

    // Both entries should still be retrievable and usable.
    EXPECT_TRUE(cache.Lookup(key1, now));
    EXPECT_TRUE(cache.Lookup(key2, now));

    // Advance to t=20; both entries are now expired.
    now += base::TimeDelta::FromSeconds(10);

    EXPECT_FALSE(cache.Lookup(key1, now));
    EXPECT_FALSE(cache.Lookup(key2, now));
}

// Try caching entries for a failed resolve attempt -- since we set the TTL of
// such entries to 0 it won't store, but it will kick out the previous result.
TEST(HostCacheTest, NoCacheZeroTTL)
{
    const base::TimeDelta kSuccessEntryTTL = base::TimeDelta::FromSeconds(10);
    const base::TimeDelta kFailureEntryTTL = base::TimeDelta::FromSeconds(0);

    HostCache cache(kMaxCacheEntries);

    // Set t=0.
    base::TimeTicks now;

    HostCache::Key key1 = Key("foobar.com");
    HostCache::Key key2 = Key("foobar2.com");
    HostCache::Entry entry = HostCache::Entry(OK, AddressList());

    EXPECT_FALSE(cache.Lookup(key1, now));
    cache.Set(key1, entry, now, kFailureEntryTTL);
    EXPECT_EQ(1U, cache.size());

    // We disallow use of negative entries.
    EXPECT_FALSE(cache.Lookup(key1, now));

    // Now overwrite with a valid entry, and then overwrite with negative entry
    // again -- the valid entry should be kicked out.
    cache.Set(key1, entry, now, kSuccessEntryTTL);
    EXPECT_TRUE(cache.Lookup(key1, now));
    cache.Set(key1, entry, now, kFailureEntryTTL);
    EXPECT_FALSE(cache.Lookup(key1, now));
}

// Try caching entries for a failed resolves for 10 seconds.
TEST(HostCacheTest, CacheNegativeEntry)
{
    const base::TimeDelta kFailureEntryTTL = base::TimeDelta::FromSeconds(10);

    HostCache cache(kMaxCacheEntries);

    // Start at t=0.
    base::TimeTicks now;

    HostCache::Key key1 = Key("foobar.com");
    HostCache::Key key2 = Key("foobar2.com");
    HostCache::Entry entry = HostCache::Entry(OK, AddressList());

    EXPECT_EQ(0U, cache.size());

    // Add an entry for "foobar.com" at t=0.
    EXPECT_FALSE(cache.Lookup(key1, now));
    cache.Set(key1, entry, now, kFailureEntryTTL);
    EXPECT_TRUE(cache.Lookup(key1, now));
    EXPECT_EQ(1U, cache.size());

    // Advance to t=5.
    now += base::TimeDelta::FromSeconds(5);

    // Add an entry for "foobar2.com" at t=5.
    EXPECT_FALSE(cache.Lookup(key2, now));
    cache.Set(key2, entry, now, kFailureEntryTTL);
    EXPECT_TRUE(cache.Lookup(key2, now));
    EXPECT_EQ(2U, cache.size());

    // Advance to t=9
    now += base::TimeDelta::FromSeconds(4);

    // Verify that the entries we added are still retrievable, and usable.
    EXPECT_TRUE(cache.Lookup(key1, now));
    EXPECT_TRUE(cache.Lookup(key2, now));

    // Advance to t=10; key1 is now expired.
    now += base::TimeDelta::FromSeconds(1);

    EXPECT_FALSE(cache.Lookup(key1, now));
    EXPECT_TRUE(cache.Lookup(key2, now));

    // Update key1, so it is no longer expired.
    cache.Set(key1, entry, now, kFailureEntryTTL);
    // Re-uses existing entry storage.
    EXPECT_TRUE(cache.Lookup(key1, now));
    EXPECT_EQ(2U, cache.size());

    // Both entries should still be retrievable and usable.
    EXPECT_TRUE(cache.Lookup(key1, now));
    EXPECT_TRUE(cache.Lookup(key2, now));

    // Advance to t=20; both entries are now expired.
    now += base::TimeDelta::FromSeconds(10);

    EXPECT_FALSE(cache.Lookup(key1, now));
    EXPECT_FALSE(cache.Lookup(key2, now));
}

// Tests that the same hostname can be duplicated in the cache, so long as
// the address family differs.
TEST(HostCacheTest, AddressFamilyIsPartOfKey)
{
    const base::TimeDelta kSuccessEntryTTL = base::TimeDelta::FromSeconds(10);

    HostCache cache(kMaxCacheEntries);

    // t=0.
    base::TimeTicks now;

    HostCache::Key key1("foobar.com", ADDRESS_FAMILY_UNSPECIFIED, 0);
    HostCache::Key key2("foobar.com", ADDRESS_FAMILY_IPV4, 0);
    HostCache::Entry entry = HostCache::Entry(OK, AddressList());

    EXPECT_EQ(0U, cache.size());

    // Add an entry for ("foobar.com", UNSPECIFIED) at t=0.
    EXPECT_FALSE(cache.Lookup(key1, now));
    cache.Set(key1, entry, now, kSuccessEntryTTL);
    EXPECT_TRUE(cache.Lookup(key1, now));
    EXPECT_EQ(1U, cache.size());

    // Add an entry for ("foobar.com", IPV4_ONLY) at t=0.
    EXPECT_FALSE(cache.Lookup(key2, now));
    cache.Set(key2, entry, now, kSuccessEntryTTL);
    EXPECT_TRUE(cache.Lookup(key2, now));
    EXPECT_EQ(2U, cache.size());

    // Even though the hostnames were the same, we should have two unique
    // entries (because the address families differ).
    EXPECT_NE(cache.Lookup(key1, now), cache.Lookup(key2, now));
}

// Tests that the same hostname can be duplicated in the cache, so long as
// the HostResolverFlags differ.
TEST(HostCacheTest, HostResolverFlagsArePartOfKey)
{
    const base::TimeDelta kTTL = base::TimeDelta::FromSeconds(10);

    HostCache cache(kMaxCacheEntries);

    // t=0.
    base::TimeTicks now;

    HostCache::Key key1("foobar.com", ADDRESS_FAMILY_IPV4, 0);
    HostCache::Key key2("foobar.com", ADDRESS_FAMILY_IPV4,
        HOST_RESOLVER_CANONNAME);
    HostCache::Key key3("foobar.com", ADDRESS_FAMILY_IPV4,
        HOST_RESOLVER_LOOPBACK_ONLY);
    HostCache::Entry entry = HostCache::Entry(OK, AddressList());

    EXPECT_EQ(0U, cache.size());

    // Add an entry for ("foobar.com", IPV4, NONE) at t=0.
    EXPECT_FALSE(cache.Lookup(key1, now));
    cache.Set(key1, entry, now, kTTL);
    EXPECT_TRUE(cache.Lookup(key1, now));
    EXPECT_EQ(1U, cache.size());

    // Add an entry for ("foobar.com", IPV4, CANONNAME) at t=0.
    EXPECT_FALSE(cache.Lookup(key2, now));
    cache.Set(key2, entry, now, kTTL);
    EXPECT_TRUE(cache.Lookup(key2, now));
    EXPECT_EQ(2U, cache.size());

    // Add an entry for ("foobar.com", IPV4, LOOPBACK_ONLY) at t=0.
    EXPECT_FALSE(cache.Lookup(key3, now));
    cache.Set(key3, entry, now, kTTL);
    EXPECT_TRUE(cache.Lookup(key3, now));
    EXPECT_EQ(3U, cache.size());

    // Even though the hostnames were the same, we should have two unique
    // entries (because the HostResolverFlags differ).
    EXPECT_NE(cache.Lookup(key1, now), cache.Lookup(key2, now));
    EXPECT_NE(cache.Lookup(key1, now), cache.Lookup(key3, now));
    EXPECT_NE(cache.Lookup(key2, now), cache.Lookup(key3, now));
}

TEST(HostCacheTest, NoCache)
{
    const base::TimeDelta kTTL = base::TimeDelta::FromSeconds(10);

    // Disable caching.
    HostCache cache(0);
    EXPECT_TRUE(cache.caching_is_disabled());

    // Set t=0.
    base::TimeTicks now;

    HostCache::Entry entry = HostCache::Entry(OK, AddressList());

    // Lookup and Set should have no effect.
    EXPECT_FALSE(cache.Lookup(Key("foobar.com"), now));
    cache.Set(Key("foobar.com"), entry, now, kTTL);
    EXPECT_FALSE(cache.Lookup(Key("foobar.com"), now));

    EXPECT_EQ(0U, cache.size());
}

TEST(HostCacheTest, Clear)
{
    const base::TimeDelta kTTL = base::TimeDelta::FromSeconds(10);

    HostCache cache(kMaxCacheEntries);

    // Set t=0.
    base::TimeTicks now;

    HostCache::Entry entry = HostCache::Entry(OK, AddressList());

    EXPECT_EQ(0u, cache.size());

    // Add three entries.
    cache.Set(Key("foobar1.com"), entry, now, kTTL);
    cache.Set(Key("foobar2.com"), entry, now, kTTL);
    cache.Set(Key("foobar3.com"), entry, now, kTTL);

    EXPECT_EQ(3u, cache.size());

    cache.clear();

    EXPECT_EQ(0u, cache.size());
}

// Try to add too many entries to cache; it should evict the one with the oldest
// expiration time.
TEST(HostCacheTest, Evict)
{
    HostCache cache(2);

    base::TimeTicks now;

    HostCache::Key key1 = Key("foobar.com");
    HostCache::Key key2 = Key("foobar2.com");
    HostCache::Key key3 = Key("foobar3.com");
    HostCache::Entry entry = HostCache::Entry(OK, AddressList());

    EXPECT_EQ(0u, cache.size());
    EXPECT_FALSE(cache.Lookup(key1, now));
    EXPECT_FALSE(cache.Lookup(key2, now));
    EXPECT_FALSE(cache.Lookup(key3, now));

    // |key1| expires in 10 seconds, but |key2| in just 5.
    cache.Set(key1, entry, now, base::TimeDelta::FromSeconds(10));
    cache.Set(key2, entry, now, base::TimeDelta::FromSeconds(5));
    EXPECT_EQ(2u, cache.size());
    EXPECT_TRUE(cache.Lookup(key1, now));
    EXPECT_TRUE(cache.Lookup(key2, now));
    EXPECT_FALSE(cache.Lookup(key3, now));

    // |key2| should be chosen for eviction, since it expires sooner.
    cache.Set(key3, entry, now, base::TimeDelta::FromSeconds(10));
    EXPECT_EQ(2u, cache.size());
    EXPECT_TRUE(cache.Lookup(key1, now));
    EXPECT_FALSE(cache.Lookup(key2, now));
    EXPECT_TRUE(cache.Lookup(key3, now));
}

// Try to retrieve stale entries from the cache. They should be returned by
// |LookupStale()| but not |Lookup()|, with correct |EntryStaleness| data.
TEST(HostCacheTest, Stale)
{
    const base::TimeDelta kTTL = base::TimeDelta::FromSeconds(10);

    HostCache cache(kMaxCacheEntries);

    // Start at t=0.
    base::TimeTicks now;
    HostCache::EntryStaleness stale;

    HostCache::Key key = Key("foobar.com");
    HostCache::Entry entry = HostCache::Entry(OK, AddressList());

    EXPECT_EQ(0U, cache.size());

    // Add an entry for "foobar.com" at t=0.
    EXPECT_FALSE(cache.Lookup(key, now));
    EXPECT_FALSE(cache.LookupStale(key, now, &stale));
    cache.Set(key, entry, now, kTTL);
    EXPECT_TRUE(cache.Lookup(key, now));
    EXPECT_TRUE(cache.LookupStale(key, now, &stale));
    EXPECT_FALSE(stale.is_stale());
    EXPECT_EQ(0, stale.stale_hits);

    EXPECT_EQ(1U, cache.size());

    // Advance to t=5.
    now += base::TimeDelta::FromSeconds(5);

    EXPECT_TRUE(cache.Lookup(key, now));
    EXPECT_TRUE(cache.LookupStale(key, now, &stale));
    EXPECT_FALSE(stale.is_stale());
    EXPECT_EQ(0, stale.stale_hits);

    // Advance to t=15.
    now += base::TimeDelta::FromSeconds(10);

    EXPECT_FALSE(cache.Lookup(key, now));
    EXPECT_TRUE(cache.LookupStale(key, now, &stale));
    EXPECT_TRUE(stale.is_stale());
    EXPECT_EQ(base::TimeDelta::FromSeconds(5), stale.expired_by);
    EXPECT_EQ(0, stale.network_changes);
    EXPECT_EQ(1, stale.stale_hits);

    // Advance to t=20.
    now += base::TimeDelta::FromSeconds(5);

    EXPECT_FALSE(cache.Lookup(key, now));
    EXPECT_TRUE(cache.LookupStale(key, now, &stale));
    EXPECT_TRUE(stale.is_stale());
    EXPECT_EQ(base::TimeDelta::FromSeconds(10), stale.expired_by);
    EXPECT_EQ(0, stale.network_changes);
    EXPECT_EQ(2, stale.stale_hits);

    // Simulate network change.
    cache.OnNetworkChange();

    EXPECT_FALSE(cache.Lookup(key, now));
    EXPECT_TRUE(cache.LookupStale(key, now, &stale));
    EXPECT_TRUE(stale.is_stale());
    EXPECT_EQ(base::TimeDelta::FromSeconds(10), stale.expired_by);
    EXPECT_EQ(1, stale.network_changes);
    EXPECT_EQ(3, stale.stale_hits);
}

// Tests the less than and equal operators for HostCache::Key work.
TEST(HostCacheTest, KeyComparators)
{
    struct {
        // Inputs.
        HostCache::Key key1;
        HostCache::Key key2;

        // Expectation.
        //   -1 means key1 is less than key2
        //    0 means key1 equals key2
        //    1 means key1 is greater than key2
        int expected_comparison;
    } tests[] = {
        { HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, 0),
            HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, 0),
            0 },
        { HostCache::Key("host1", ADDRESS_FAMILY_IPV4, 0),
            HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, 0),
            1 },
        { HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, 0),
            HostCache::Key("host1", ADDRESS_FAMILY_IPV4, 0),
            -1 },
        { HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, 0),
            HostCache::Key("host2", ADDRESS_FAMILY_UNSPECIFIED, 0),
            -1 },
        { HostCache::Key("host1", ADDRESS_FAMILY_IPV4, 0),
            HostCache::Key("host2", ADDRESS_FAMILY_UNSPECIFIED, 0),
            1 },
        { HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, 0),
            HostCache::Key("host2", ADDRESS_FAMILY_IPV4, 0),
            -1 },
        { HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, 0),
            HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED,
                HOST_RESOLVER_CANONNAME),
            -1 },
        { HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED,
              HOST_RESOLVER_CANONNAME),
            HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED, 0),
            1 },
        { HostCache::Key("host1", ADDRESS_FAMILY_UNSPECIFIED,
              HOST_RESOLVER_CANONNAME),
            HostCache::Key("host2", ADDRESS_FAMILY_UNSPECIFIED,
                HOST_RESOLVER_CANONNAME),
            -1 },
    };

    for (size_t i = 0; i < arraysize(tests); ++i) {
        SCOPED_TRACE(base::StringPrintf("Test[%" PRIuS "]", i));

        const HostCache::Key& key1 = tests[i].key1;
        const HostCache::Key& key2 = tests[i].key2;

        switch (tests[i].expected_comparison) {
        case -1:
            EXPECT_TRUE(key1 < key2);
            EXPECT_FALSE(key2 < key1);
            break;
        case 0:
            EXPECT_FALSE(key1 < key2);
            EXPECT_FALSE(key2 < key1);
            break;
        case 1:
            EXPECT_FALSE(key1 < key2);
            EXPECT_TRUE(key2 < key1);
            break;
        default:
            FAIL() << "Invalid expectation. Can be only -1, 0, 1";
        }
    }
}

} // namespace net
